Remove all adjacent duplicates in string

Time: O(N); Space: O(N); easy

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed the answer is unique.

Example 1:

Input: s = “abbaca”

Output: “ca”

Explanation:

  • For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move.

  • The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.

Constraints:

  • 1 <= len(S) <= 20000

  • S consists only of English lowercase letters.

Hint:

  1. Use a stack to process everything greedily.

[8]:

class Solution1(object):
    def removeDuplicates(self, S):
        """
        :type S: str
        :rtype: str
        """
        result = []

        for c in S:
            if result and result[-1] == c:
                result.pop()
            else:
                result.append(c)

        return "".join(result)

[9]:

sol = Solution1()
s = "abbaca"
assert sol.removeDuplicates(s) == "ca"